#define  _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

#include<vector>

using namespace std;


//摆动序列，子序列问题
//这是我做的第二个子序列问题，首先先考虑是否是多状态，划分为向上和向下两种情况
//子序列问题的步骤还需要熟练与子数组要区分开
//这个题的状态转移方程的逻辑和递增子序列是差不多的
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();

        //创建dp表
        vector<int> f(n, 1), g(n, 1);

        int ret = 1, ans = 1;
        //填表
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i]) f[i] = max(g[j] + 1, f[i]);
                else if (nums[j] > nums[i]) g[i] = max(f[j] + 1, g[i]);
            }
            ret = max(ret, f[i]);
            ans = max(ans, g[i]);
        }

        //返回值
        return max(ret, ans);
    }
};


int main()
{
	return 0;
}